package bfs;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class 火星词典 {
	public String alienOrder(String[] words) {
        Set<char[]> si=new HashSet<>();   //收集比较信息，选用set，以防止重复收集
        int n=words.length;
        //二重for循环，两两比较，获得两两字符的大小关系
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                String s=words[i];
                String t=words[j];
                int len=Math.min(s.length(),t.length());
                for(int k=0;k<len;k++){
                    char a=s.charAt(k),b=t.charAt(k);
                    //由于words有序，因此只要字符不等,一定有a<b
                    if(a!=b){
                        si.add(new char[]{a,b});
                        break;
                    }
                    else{
                        //处理 [abc,ab]的情况
                        if(k==len-1&&s.length()>t.length()){
                            return "";
                        }
                    }
                    
                }
            }
        }

        Map<Character,Integer> in=new HashMap<>();  //统计入度
        //初始化，将需要排序的字符加入哈希表
        for(int i=0;i<n;i++){
            String sc=words[i];
            for(int j=0;j<sc.length();j++){
                in.put(sc.charAt(j),0);
            }
        }



        Map<Character,List<Character>> edges=new HashMap<>(); //统计字符c的邻边
        //建图
        for(char[] t:si){
            //a->b
            char a=t[0],b=t[1];
            //如果字符不存在，建立邻边数组
            if(edges.containsKey(a)==false){
                edges.put(a,new ArrayList<>());
            }
            edges.get(a).add(b);
            in.put(b,in.get(b)+1);
        }

        Queue<Character> q=new LinkedList<>();
        StringBuilder ret=new StringBuilder();
        //初始化
        for(Map.Entry<Character,Integer> tmp:in.entrySet()){
            if(tmp.getValue()==0){
                q.add(tmp.getKey());
            }
        }
        //模拟
        while(!q.isEmpty()){
            char c=q.poll();
            ret.append(c);
            for(char k:edges.getOrDefault(c,new ArrayList<>())){
                in.put(k,in.get(k)-1);
                if(in.get(k)==0){
                    q.add(k);
                }
            }
        }
        //判断是否有环
        for(Map.Entry<Character,Integer> x:in.entrySet()){
            if(x.getValue()!=0){
                return "";
            }
        }
        return ret.toString();
    }
}
